The present invention relates to computer-assisted methods and apparatus for generating or compiling electronic designs such as designs for digital integrated circuits. More specifically, the invention relates to improvements in using timing information while compiling electronic designs.
Electronic design automation (“EDA”) is becoming increasingly complicated and time consuming, due in part to the greatly increasing size and complexity of the electronic devices designed by EDA tools. Such devices include general purpose microprocessors as well as custom logic devices including Application Specific Integrated Circuits (“ASICs”). The design of even the simplest of these devices typically involves generation of a high level design, logic simulation, generation of a network, timing simulation, etc.
Meeting timing requirements is essential to the correct operation of an integrated circuit. For example, for a plurality of D-type flip-flops (“DFFs”) to feed through some logic to another plurality of DFFs, it is generally required that the signals from the first set of DFFs must finish propagating through any intermediate logic and have settled to their final state on the D-input of each of the destination DFFs before the next rising edge of the clock. If the delay through the resulting logic is greater than the time between rising clock edges, then the state that the destination DFFs will hold on the next clock edge will be undefined.
In order to meet timing requirements optimization methods are applied. Optimizing a circuit can occur at any time during synthesis, technology mapping, clustering, placement, or routing. Most optimization methods require an identification of “critical connections” between circuit elements or blocks. Emphasis is made during optimization to optimize the timing of those connections having the greatest criticality. For example, during placement, the placement algorithm will attempt to keep those elements or blocks having a critical connection in a configuration where the connection would be made with as little delay as possible. A critical path is a path that has the longest delay. In fact, there may be several critical paths in a circuit. The cycle time of the clock that controls the DFF's at the beginning and end of the path cannot be any less than this delay. A critical path may consist of one or more connections, and all those connections will be critical.
Several different methods are used in circuit optimization to determine which connections are critical and therefore need to be made via fast wiring lines to avoid slowing down the circuit. Optimization is typically required in the conversion or placement of an electronic design in the form of a netlist into a physical device, such as an FPGA or CPLD. A traditional recursive partitioning algorithm will recursively divide an electronic design in half and repeat the division until the design is fully placed into the device. Partitioning methods may be applied to flat architectures such as gate arrays but are especially suitable for hierarchical architectures such as Altera's APEX 20K family of devices. In hierarchical architectures, crossing center boundaries involves significant costs in the form of delays added. Typically, as an electronic design is divided in half and again in half, the placement tool will attempt to minimize the wires which cross between physical half A and physical half B of the physical device to avoid lengthy delays across critical paths. As the wire placement or “cut” crosses boundaries lower in the hierarchy, smaller delays are added for each cut until the point where the wire placement between two cells occurs entirely within a cell and no additional delay is added.
The goal of this process is to obtain a faster circuit, generally when the longest delay of the placed design into the physical device is minimized. This measure is often stated in terms of a faster frequency for the circuit. After every cut of the design into the physical part the user or tool will know the actual delays contributed by that cut since for any such physical electronic device, the logic delays across the boundaries are known for that architecture. Since interconnect delays for the architecture are known for a fixed distance and load, a fully placed netlist has a deterministic timing analysis. A partially placed netlist, however, has a known timing analysis only if the placement algorithm gives the timing analyzer an estimate of unknown interconnect delays for edges not yet routed or placed.
A netlist with nodes and edges annotated with their electrical delay allows the user to compute, for each node and edge, the maximum delay from a source or to a destination, and hence the length of the longest path through that node or edge. Given a target delay (constraint) on an A to B path, the slack delay for that path is the (most stringent) constraint minus the actual delay of the path For a given node or edge, the slack of the node or edge is the minimum slack over all paths which contain the node or edge. All these values are well-defined in a synchronous netlist, and computable in linear time with several graph traversals.
A critical path is one which has the minimum slack over all paths. In a single-clock system with a single global fmax (register—register) delay constraint, this is equivalent to the path with the maximum delay. In a multi-clock system with different fmax specifications for different clocks, or with specific point-to-point path constraints, minimum slack is not equivalent to maximum delay. The goal of a timing driven compilation is to maximize the worst-case (minimum) slack.
One problem with the use of recursive partitioning as an algorithm for timing-driven placement is that the true path delays are not known in the early stages of placement. Therefore identifying the critical paths before the netlist has been placed is difficult. The partitioning algorithm can minimize the number of critical nets which are cut early on, yet these nets may not be the true critical nets by the time the partitioning tool has proceeded several levels deep in the placement, due to the delays added by the cuts. This problem is intrinsic whether or not the target architecture is hierarchical, but is exacerbated by non-uniform delays in a hierarchical part.
What is needed therefore is an improved method for estimating the delays for edges or connections which have not yet been placed in order to identify accurately the critical paths.